package problem375;


//375.猜数字大小2
//https://leetcode.cn/problems/guess-number-higher-or-lower-ii/

class Solution {
    int[][] dp;
    public int getMoneyAmount(int n) {
        dp = new int[n+1][n+1];
        return dfs(1,n);
    }
    public int dfs(int left, int right) {
        if(left >= right) return 0;
        if(dp[left][right] != 0) return dp[left][right];

        int ret = Integer.MAX_VALUE;
        for(int i = left; i<=right; i++) {
            int x = dfs(left, i-1);
            int y = dfs(i+1, right);
            ret = Math.min(ret, Math.max(x, y) + i);
        }
        dp[left][right] = ret;
        return ret;
    }
}